The present invention relates generally to the field of digital computers and, more particularly, to the field of executive function implementations.
An executive currently is defined as a program which regulates when each portion of the application software has access to the various resources of the computer. The application software informs the executive of its needs and available resources by calling executive service request (ESR) routines. Often several ESR's share common subroutine components. The one or more subroutine components of an ESR are called executive functions.
Executive functions are usually implemented in software. Occasionally, firmware implementations are used for speed improvement. While statistics in the literature vary, firmware implementations usually obtain a two to three times improvement in executive function execution speed. Their speed improvement is derived primarily through the elimination of most of the instruction fetches associated with software implementations. Executive functions make heavy use of data structures stored in memory. Consequently, the speed of the data access cycle is the major limiting factor preventing still further speed improvement through microprogramming.
The throughput of multiprocessing systems increases less than linearly with an increase in the number of processors. Each processor is burdened not only with the coordination of its own activity but also with at least some portion of the activity of the processors to which it is connected. Increasing the number of processors increases the overhead in each processor. Eventually, a point is reached where adding a processor has a negligible effect or even decreases the usable throughput of the system. This is because the increase in overhead in all the processors totals more than the capacity of the added processor.
One of the major manifestations of executive overhead is table searching. It is encountered in dispatch checking, real-time clock management, resource management, and event binding. To illustrate the effect, consider a multiprocessing system employing a common table. A configuration consisting of a single stand-alone processor spends some portion of its time serially searching a table. When a second processor is added to improve system capacity, both processors are required to search the same common table. The added contribution of processing from the second processor roughly doubles the original size of the table. Increasing the size of the table, and hence the time spent searching the table, leaves less time in each processor for other processing. The time each processor has available for other processing continues to decrease as additional processors are added.
Since table searching is an important component determining the speed of executive processing, executive software often exhibits similar characteristics. A good example is a common task table in a multiprocessing system in which the highest priority task ready for execution is dispatched on the first available processor. The dispatch check performed by each processor must examine all the tasks in the system. The larger the system, the more tasks each processor must examine, and consequently, the less application work performed by each processor.
Message processing in distributed processing systems also suffers from diminishing returns as processors are added. One example is SEAMOD, a proposed Navy distributed command and control system architecture. The processors of the system are interconnected through a high-speed message bus. It has been estimated in this proposed system that up to 58 percent more processors are required, depending on the configuration, simply to perform the executive functions associated with message traffic of the distributed system.
Another example of the problem is illustrated by an experiment performed by the developers of the Shipboard Integrated Processing and Display System (SHINPADS) for the Canadian Navy. They wished to demonstrate two megabits of data traffic on a triaxial cable bus interconnecting ten AN/UYK-20 computer emulators. Each computer generated and received one-tenth of the two megabit traffic. Using 200-bit messages, this means that each computer generated and received one message every millisecond. It was found that the one millisecond was consumed almost entirely by the executive software. Not only does such a system fail to apply the power of ten computers to the performance of the application work, but it fails to do almost any useful work.
The problem is that the execution speed of the executive functions is too slow in a conventional processor. The executive functions considered in the SEAMOD example, when executed on an AN/UYK-20 computer, would require 1.12 milliseconds per message. The motivation for high-speed execution of executive functions in hardware is the reduction of overhead in each processor of a multiprocessing or distributed processing system to extend the point of diminishing returns to a larger number of processors.